package newcoder_exp.justPractise;
import java.util.*;
import linked.*;


public class NC51 {
    public class Solution {
        public ListNode mergeKLists(ArrayList<ListNode> lists) {
            
            List<ListNode> cur = new ArrayList<>(lists);
            int idx = 0;
            while (cur.size() > 1) {
                List<ListNode> temp = new ArrayList<>();
                idx = 0;
                if (cur.size() % 2 == 1) {
                    temp.add(cur.get(0));
                    idx++;
                }
                for (int i = idx; i < cur.size(); i += 2) {
                    temp.add(merge(cur.get(i), cur.get(i + 1)));
                }
                cur = temp;
            }
            return cur.get(0);
        }

        public ListNode divide(ArrayList<ListNode> lists, int lo, int hi) {
            if (lo == hi) {
                return lists.get(lo);
            }
            if (lo > hi) {
                return null;
            }
            int mid = (hi - lo) / 2 + lo;
            ListNode left = divide(lists, lo, mid);
            ListNode right = divide(lists, mid + 1, hi);
            return merge(left, right);
        }


        public ListNode merge(ListNode p, ListNode q) { 
            ListNode res = new ListNode(), result = res;
            while (p != null && q != null) {
                if (p.val <= q.val) {
                    res.next = p;
                    p = p.next;
                } else {
                    res.next = q;
                    q = q.next;
                }
                res = res.next;
            }
            if (p == null) p = q;
            res.next = p;
            return result.next;
        }
    }
}
